Codechef
Hello, I created that page to show your solutions of the march codechef cook off contest. Bishops Travelling Plan Palindrome (Alexis)Hi everyone, I had a small problem with that exercise. If you did it well, could you help me, I can't pass some tests but I don't know why. My code: http://pastebin.com/Ak2B9mYf Thank you in advance — Victor's solution: http://pastebin.com/8X0JfRNA Gosh you've not made your life simple! The power function looks correct and efficient to me, even though it can be made shorter (see my solution). However, N (the maximum length) is so big that you can't even run a loop to calculate every power one by one, so you'll have to think of a better way. You know that S = 26+26²+26³+…+26^k = 26*(26^k-1)/(26-1) <=> 25*S = 26(26^k+1), thanks to the formula for the sum of geometrical progressions. You can compute 26*(26^k-1) pretty easily, but the problem is dividing by 25. Fortunately, number theory saves us here, because, when working with modulos, dividing by some number is the same as multiplying by it's inverse, which in this case is 280000002 (because (25*280000002)%1000000007 = 1). See Wikipedia for more info on that subject. So now we have the sum 26+26²+…+26^k, we just have to multiply it by 2 and add a last power to the sum if N%2 1. But be really careful at all times to apply %1000000007 so that your integers don't reach the limit or simply get bigger than 1000000007 at the end. If you need extra explanation (especially on the number theory part), feel free to ask. ;) __ Thank's a lot Victor :) — Floris told me a very clever way to divide by 25 : while(curr%25 != 0) curr += MOD; curr /= 25; It's probably much easier to understand that way. (It's a little slower, but 25 is really small anyway.) __ (Henri) Hi everyone, I don't understand the part with the modulos (What is %1000000007 ?). Could someone give me some explanation about it ? — It is the rest of the division of a number by 1000000007. As an example : 26%5=1, because 26=5*5+1 ; 32%6=2; because 32=6*5+2, etc. __ (Henri) I know what is a modulo, but why must we use %1000000007 to solve this problem ? What is the purpose of that ? — I think it is to avoid the int limit. If a number go upper than 2147483647, it can't be contained in a int (and is therefore modulate by 2147483647). For the __int64, this limit is of 9223372036854775807. As the answer to the problem can be VERY VERY VERY big, we have to modulate the answer. And for everyone to have the same answer, they chose %1000000007. __ Thank's for your answer =) Level of difference The ball and cups (Simon T) : Nobody put his solution, so I put mine ^^ http://pastebin.com/76gKzpAm (Victor) This might be simpler: C = flipLow + flipUp - C (instead of the conditions). But it's trickier to find and/or prove. ;) (Simon) is it trickier to prove ? you manipulate a bit the expressions : *C + = (flipLow+flipUp)-C * 2 <=> C = flipLow + flipUp - C AND *C -= C * 2-(flipLow+flipUp) <=> C = flipLow + flipUp - C. And it's done ^^ (Victor) For some reason I thought there were divisions in the calculations. Feeling quite dumb now. :P (Apparently that stupid editor recognizes stars as list items…)